Small set (combinatorics)
In combinatorial mathematics, a small set of positive integers
is one such that the infinite sum
converges. A large set is any other set of positive integers (i.e. one whose sum diverges).
Examples
- The set of all positive integers is known to be a large set (see Harmonic series), and so is the set obtained from any arithmetic sequence (i.e. of the form an + b with a ≥ 0, b ≥ 1 and n = 0, 1, 2, 3, ...) where a = 0, b = 1 give the multiset and a = 1, b = 1 give .
- The set of square numbers is small (see Basel problem). So is the set of cube numbers, the set of 4th powers, and so on... And so is the set of any polynomial numbers of degree k ≥ 2 (i.e. of the form , with a ≥ 1, ai ≥ 0 for all i ≥ 1 but ai > 0 for at least one i ≥ 2, and n = 0, 1, 2, 3, ...). Polynomial numbers of degree k < 2 give an arithmetic sequence (which form a large set.) Polynomial numbers of degree 2 give a quadratic sequence which form a small set. Polynomial numbers of degree 3 give a cubic sequence which also form a small set. And so on...
- The set of powers of 2 is known to be a small set, and so is the set of any geometric sequence (i.e. of the form abn with a ≥ 1, b ≥ 2 and n = 0, 1, 2, 3, ...).
- The set of numbers whose decimal representations exclude 7 (or any digit one prefers) is small. That is, for example, the set
- is small. (This has been generalized to other bases as well.) See Kempner series.
Properties
- A union of finitely many small sets is small, as the sum of two convergent series is a convergent series. A union of infinitely many small sets is either a small set (e.g. the sets of p2, p3, p4, ... where p is prime) or a large set (e.g. the sets for k > 0). Also, a large set minus a small set is still large. A large set minus a large set is either a small set (e.g. the set of all prime powers pn with n ≥ 1 minus the set of all primes) or a large set (e.g. the set of all positive integers minus the set of all positive even numbers). In set theoretic terminology, the small sets form an ideal.
- is dense in the uniform norm topology of continuous functions on a closed interval. This is a generalization of the Stone–Weierstrass theorem.
Open problems
There are many sets about which it is not known whether they are large or small.
Paul Erdős famously asked the question of whether any set that does not contain arbitrarily long arithmetic progressions must necessarily be small. He offered a prize of $3000 for the solution to this problem, more than for any of his other conjectures, and joked that this prize offer violated the minimum wage law.[1] This question is still open.
Notes
References
- A. D. Wadhwa (1975). An interesting subseries of the harmonic series. American Mathematical Monthly 82 (9) 931–933.